/*================================================================
*   文件名称：main.cpp
*   创 建 者：yang qiang
*   创建日期：2019年01月04日
*   描    述：
*   Copyright (C) 2019 All rights reserved.
*   
================================================================*/


#include <iostream>
#include <vector>
#include <stack>

using namespace std;

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        if( !root )
            return res;
        
        stack<TreeNode *> st;
        TreeNode *pre = root;
        TreeNode *p = NULL;

        st.push(root);
        while( !st.empty() ){
            p = st.top();
            if( (!p->left && !p->right) || (pre == p->left || pre == p->right) ){
                res.push_back(p->val);
                st.pop();
                pre = p;
            }else{
                if( p->right )
                    st.push(p->right);
                if( p->left )
                    st.push(p->left);
            }

        }

        return res;
        
    }
};

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        if(!root){
            return res;
        }      

        stack<TreeNode*> s;
        TreeNode* node = root;
        TreeNode* prenode = NULL;

        while(node || !s.empty()){
            while(node){
                s.push(node);
                node = node->left;
            }

            node = s.top();
            if(node->right && node->right != prenode){
                node = node->right;
            }else{
                s.pop();
                res.push_back(node->val);
                prenode = node;
                node = NULL;
            }
        }

        return res;
    }
};